package com.likeycy.my.sort.cmp;

/**
 * @ClassName: SelectionSort
 * @Description: 比较算法：选择排序
 * @Author: sodagreen
 * @Date: 2021/3/26 23:37
 * @Version: 1.0
 */
public class SelectionSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int end = array.length-1; end >0 ; end--) {
            // 保存第一轮找出来的最大值所在的索引
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                // 如果当前循环下标位置的值大于上一轮判断时候找到的最大值，那么将当前索引赋值给变量
                // 直到循环结束，找到最大值所在的索引位置
                if (cmp(maxIndex, end) <= 0) {
                    maxIndex = begin;
                }
            }
            swap(maxIndex, end);
        }
    }

    /**
     * 备份
     */
    private void selectionSortByBackup() {
        for (int end = array.length-1; end >0 ; end--) {
            // 保存第一轮找出来的最大值所在的索引
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                // 如果当前循环下标位置的值大于上一轮判断时候找到的最大值，那么将当前索引赋值给变量
                // 直到循环结束，找到最大值所在的索引位置
                if (cmp(maxIndex, begin) <= 0) {
                    maxIndex = begin;
                }
            }
            T temp = array[maxIndex];
            // 将末尾的值赋值给找到的最大值所在索引位置
            array[maxIndex] = array[end];
            // 将最大值直接放到数组的最后面，这样第一轮循环找到了数组最大值，下一轮循环继续如此操作即可
            array[end] = temp;
        }
    }
}
